package src.greed;

import java.util.ArrayList;
import java.util.List;

public class no763 {//划分字母区间

    public List<Integer> partitionLabels(String s) {
        //用一个hash数组统计每个字符出现的最远位置
        List<Integer> res = new ArrayList<>();
        int left = 0, right = 0;
        int[] hash = new int[26];
        for (int i = 0; i < s.length(); i++) {
            hash[s.charAt(i) - 'a'] = i;
        }

        for (int i = 0; i < s.length(); i++) {
            right = Math.max(right, hash[s.charAt(i) - 'a']);  //每次更新right的最大值，知道right==i
            if (right == i) {
                res.add(right - left + 1);
                left = i + 1;  //出现一个片段时，更新left值，开始进入下一段字符串
            }
        }
        return res;

    }
}
